package com.example.question.dp.dp2;

import java.util.Arrays;

public class Code12_279 {
    public static void main(String[] args) {
        Code12_279 code = new Code12_279();
        System.out.println("code.numSquares(13) = " + code.numSquares(13));
        System.out.println("code.numSquares(12) = " + code.numSquares(12));
        System.out.println("code.numSquares(51) = " + code.numSquares(51));
        System.out.println("code.numSquares(10000) = " + code.numSquares(10000));
        System.out.println("code.numSquares(9999) = " + code.numSquares(9999));
        System.out.println("code.numSquares(8935) = " + code.numSquares(8935));
    }

    public int numSquares1(int n) {
        int upper = (int) Math.sqrt(n);
        int[][] memo = new int[upper + 1][n + 1];
        return dfs(n, 1, upper, memo);
    }


    private int dfs(int n, int index, int upper, int[][] memo) {
        if (n < 0 || index > upper) {
            return -1;
        }
        if (n == 0) {
            return 0;
        }
        if (memo[index][n] != 0) {
            return memo[index][n];
        }

        int minCount = Integer.MAX_VALUE;
        for (int i = upper; i >= 1; i--) {
            int res = dfs(n - i * i, i, upper, memo);
            if (res >= 0) {
                minCount = Math.min(res + 1, minCount);
            }
        }
        memo[index][n] = minCount;
        return minCount;
    }

    public int numSquares(int n) {
        int upper = (int) Math.sqrt(n);
        return numSquares(n, upper);
    }

    public int numSquares(int n, int upper) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 1; i <= upper; i++) {
            dp[i * i] = 1;
        }

        for (int i = 2; i < n + 1; i++) {
            if (dp[i] == 1) {
                continue;
            }
            int count = Integer.MAX_VALUE;
            for (int j = upper; j >= 1; j--) {
                int square = j * j;
                // 选出dp[i - square]里面最小一个即可
                if ((i > square) && dp[i - square] != Integer.MAX_VALUE) {
                    count = Math.min(count, dp[i - square]);
                }
            }
            dp[i] = (count + 1);
        }
        return dp[n];
    }
}
